﻿#include"AVLTree.h"

int _Height(Node* root)
{
	if (root == nullptr)
		return 0;
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool _IsBalanceTree(Node* root)
{
	// 空树也是AVL树 
	if (nullptr == root)
		return true;
	// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差 
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	int diff = rightHeight - leftHeight;
 // 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者 
		 // pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树 
		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "⾼度差异常" << endl;
			return false;
		}
	if (root->_bf != diff)
	{
		cout << root->_kv.first << "平衡因⼦异常" << endl;
		return false;
	}
	// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树 
	return IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

// 测试代码 
void TestAVLTree1()
{
	AVLTree<int, int> t;
	// 常规的测试⽤例 
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	// 特殊的带有双旋场景的测试⽤例 
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.Insert({ e, e });
	}
	t.InOrder();
	cout << t.IsBalanceTree(t.GetRoot()) << endl;
}

// 插⼊⼀堆随机值，测试平衡，顺便测试⼀下⾼度和性能等 
void TestAVLTree2()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << "Insert:" << end2 - begin2 << endl;
	cout << t.IsBalanceTree() << endl;
	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;
	size_t begin1 = clock();
	// 确定在的值 
	/*for (auto e : v)
	{
	t.Find(e);
	}*/
	// 随机值 
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << endl;
}


int main()
{
	TestAVLTree1();
}